判断一个二叉树是否是镜像二叉树。

LeetCode 101. Symmetric Tree

解答1[Java]：

核心思想

使用递归的方式，首先，一次输入两个节点，然后对比两个节点的值，递归判断第一个节点的左子树节点和第二个节点的右子树节点是否相同，递归判断第一个节点的右子树节点和第二个节点的左子树节点是否相同。递归开始的时候，函数的两个实参都填 root 节点即可。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }

    public boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null)
            return true;
        if (t1 == null || t2 == null)
            return false;
        return (t1.val == t2.val) && isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right);
    }
}

复杂度分析

时间复杂度

$O(n)$

空间复杂度

最坏情况下，树退化成一个单链表，递归空间复杂度变成 $O(n)$。

解答2[Java]：

核心思想

使用队列作为辅助。每次都从队列中弹出来两个对象，比较他们的值，如果相同，把他们的子节点按照以下顺序存入队列中：①第一个节点的左节点②第二个节点的右节点③第一个节点的右节点④第二个节点的左节点。

队列的前两个元素都存成根节点。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode t1 = q.poll();
            TreeNode t2 = q.poll();
            if (t1 == null && t2 == null)
                continue;
            if (t1 == null || t2 == null)
                return false;
            if (t1.val != t2.val)
                return false;
            q.add(t1.left);
            q.add(t2.right);
            q.add(t1.right);
            q.add(t2.left);
        }
        return true;
    }
}

参考

1. 剑指Offer 27. 镜像二叉树和这道题很像。